Most electronic devices utilize a physical data storage hardware, such as a hard drive (also commonly known as “hard disk”) and/or a Multi-media card (MMC), and a multilayered software architecture to manage how data is stored and retrieved. In this multilayered software architecture, In many cases, data stored in an electronic device is of high importance, and needs protection against malicious or unverifiable modifications, which is known as data integrity protection. For example, telecommunication handsets have embedded MMCs housing operating system related data that is the frequent target of malicious alternations aim1ng to hijack the control of a device or to steal sensitive information. On the other hand, a valid update or change to the data stored on a device is often needed. For example, the manufacturer frequently releases Over-The-Air (OTA) software updates to the telecommunications handsets to fix bugs or upgrade software system features. Therefore, data integrity protection is also required to accommodate the run-time update to the data on devices.
One common approach of data integrity protection is to verify the data on the layer of block device. Block device, an abstract layer in the above-mentioned multilayered software architecture, manipulates data in fixed-size blocks, and controls the data transfer between the layer of file system and the layer of actual physical hardware. Data stored on a block device can be verified by applying a cryptographic hash function to the current contents of the block device as a whole to obtain a hash checksum and comparing this hash checksum against a precomputed known good checksum value. The known good checksum value is the result of applying the same hash function to the known good contents of a block device. Some methods of calculating the checksum utilize calculation of a cryptographic hash tree. The root of the hash tree, also called “root hash”, is the calculated checksum used to check against the known good checksum value. When the calculated checksum matches the known good checksum, the block device contents are considered verified, i.e., the contents are known good. When an authenticated change is applied to a verified block device, new known good checksum has to be provided, and thereafter, the device can be verified by comparing the calculated hash checksum to the new known good hash checksum. It should be pointed out that the hash checksum calculation is sensitive to not only the contents stored in each data block but also the distribution order of data blocks on a block device such that even if a block device includes the same set of data blocks as a the verified or known good block device. Consequently, to maintain the feasibility of utilizing the pre-computed known-good hash checksum for data integrity verification after update, the update to the block devices to be applied in a deterministic block-by-block manner, i.e., the change to each data block and the distribution of data blocks after update are pre-determined, from which a new known good hash checksum is pre-computed. Such an update method is known as block-based update. However, many manufacturers use the file-based update method in which the update is applied by removing, adding, and/or overwriting files in the layer of file system, and the actual changes to the underlying block device layer are non-deterministic, i.e., the change to each data block and the distribution of data blocks after update are unknown now. That is, the pre-computed known good checksum value can no longer be used to verify the data on device after a file-based update is applied. As a result, the above-described methodology cannot be used to verify the data integrity of devices with run-time file-based update. Accordingly, there is a need for methods of efficiently verifying the data integrity of block devices which can accommodate the file-based update on run time.